package com.jack.leetcode.eachProblem07;

public class 地下城游戏 {

    public static void main(String[] args) {
        int[][] a = {
                {-2, -3, 3},
                {-5, -10, 1},
                {10, 30, -5}
        };
        System.out.println(calculateMinimumHP(a));
    }

    public static int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        if (dungeon[m - 1][n - 1] > 0) dungeon[m - 1][n - 1] = 0;

        for (int i = m - 2; i >= 0; i--) {
            dungeon[i][n - 1] = dungeon[i][n - 1] + dungeon[i + 1][n - 1];
            if (dungeon[i][n - 1] > 0) dungeon[i][n - 1] = 0;
        }

        for (int i = n - 2; i >= 0; i--) {
            dungeon[m - 1][i] = dungeon[m - 1][i] + dungeon[m - 1][i + 1];
            if (dungeon[m - 1][i] > 0) dungeon[m - 1][i] = 0;
        }

        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dungeon[i][j] = dungeon[i][j] + Math.max(dungeon[i + 1][j], dungeon[i][j + 1]);
                if (dungeon[i][j] > 0) {
                    dungeon[i][j] = 0;
                }
            }
        }
        return dungeon[0][0] > 0 ? 1 : -dungeon[0][0] + 1;
    }
}
